import bisect

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.db = dict()

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.db:
            self.db[key].append([timestamp, value])
        else:
            self.db[key] = [[timestamp, value]]

    def get1(self, key: str, timestamp: int) -> str:
        if key not in self.db:
            return ""
        list1 = self.db.get(key)
        if list1[0][0] > timestamp:
            return ""
        current_idx = 0
        begin_idx = 0
        end_idx = len(list1) - 1
        while begin_idx < end_idx:
            current_idx = (begin_idx + end_idx) // 2
            if current_idx == begin_idx:
                current_idx += 1
                break
            if current_idx == end_idx:
                break
            if list1[current_idx][0] == timestamp:
                return list1[current_idx][1]
            elif list1[current_idx][0] < timestamp:
                begin_idx = current_idx
            else:
                end_idx = current_idx
        if list1[current_idx][0] > timestamp:
            current_idx -= 1
        return list1[current_idx][1]


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.db:
            return ""
        list1 = self.db.get(key)
        idx = bisect.bisect_left(list1, [timestamp, "z"*101])
        if idx == 0:
            return ""
        else:
            return list1[idx - 1][1]


# Your TimeMap object will be instantiated and called as such:
obj = TimeMap()
obj.set("love","high",10)
obj.set("love","low",20)

param_2 = obj.get("love",10)
print(param_2)
param_2 = obj.get("love",15)
print(param_2)
param_2 = obj.get("love",20)
print(param_2)
param_2 = obj.get("love",25)
print(param_2)
